2.9

有一学习问题，其中每个实例都由 n 个布尔值属性 $a_1, a_2, ..., a_n$ 的合取来描述。因此，一个典型的实例如下：

现考虑一个假设空间 $H$ 中，每个假设是这些属性约束的析取，例如：

设计一算法，它经过一系列的样例训练后输出一个一致的假设（如果存在的话）。算法的时间要求为 n 和训练样例数目的多项式函数。

---

解答：

为了理解问题，我先用一个最简单的例子来重述一下。

每个实例是由两个布尔值属性 $a_1, a_2$ 的合取来描述，即实例是 $(a_1=T) \land (a_2=F)$ 的形式。假设空间 $H$ 中的每个假设是这两个属性的析取，即假设是 $(a_1=T) \lor (a_2=F)$ 的形式。现在要设计一个算法，通过一系列的样例训练后输出一个一致的假设。

所谓一致的假设，就是能够覆盖所有正例而不包含反例的假设。比如，正例是 $(a_1=T) \land (a_2=F)$， 以及 $(a_1=F) \land (a_2=T)$ ，反例是 $(a_1=T) \land (a_2=T)$ 和 $(a_1=F) \land (a_2=F)$。这时就不存在一个一致的假设。原因是在所有可能的假设中，没有一个假设能够同时包含正例和排除反例。所有可能的假设如下：

h₁: $(a_1=T) \lor (a_2=F)$，会包含反例。

h₂: $(a_1=T) \lor (a_2=T)$，会包含反例。

h₃: $(a_1=F) \lor (a_2=F)$，也会包含反例。

h₄: $(a_1=F) \lor (a_2=T)$，仍然包含反例。

所有可能的析取项均被反例覆盖，因此无法构造出满足条件的假设。

另一个例子是，正例是 $(a_1=T) \land (a_2=T)$ ，$(a_1=T) \land (a_2=F)$，$(a_1=F) \land (a_2=T)$，反例是 $(a_1=F) \land (a_2=F)$ 。这时就存在一个一致的假设，即 $(a_1=T) \lor (a_2=T)$，它能够包含所有正例而排除反例。

以下是 DeepSeek 的解答：

题目是说，每个实例是由n个布尔属性的合取来描述，比如像(a1=T) ∧ (a2=F) ∧ ... ∧ an=T这样的形式。然后假设空间H中的每个假设是这些属性约束的析取，比如(a1=T) ∨ (a2=F) ∨ ...这样的。我们的任务是设计一个算法，在给定一系列训练样例后，输出一个与这些样例一致的假设，如果存在的话。而且算法的时间要是n和样例数的多项式函数。

首先，我得理解什么是“一致的假设”。这里的假设应该正确分类所有的训练样例。也就是说，对于每个正例，假设必须被满足；对于每个反例，假设不能被满足。或者可能要看具体的分类任务的设定。比如，可能问题是一个二分类问题，样例被标记为正例或负例，而假设需要正确预测它们的标签。假设当实例满足假设时，被分类为正例，否则为负。因此，算法需要找到这样的一个析取式，使得所有正例满足该假设，所有负例不满足该假设。

假设空间中的每个假设是一些属性的约束的析取。比如，假设可能像a1=T ∨ a3=F。这里的每个项是单个属性的等于某个值的约束，然后整体是它们的析取。所以一个假设由若干这样的项组成，任何一个项成立，则假设成立。

现在的问题是，如何从训练数据中学习这样的假设。如果存在这样的假设，就输出它；否则可能输出不存在。但题目可能保证存在的话才需要输出，否则可能不需要考虑，题目只说输出一致的假设如果存在的话。

那我们的任务转化为，找到一个析取式H，使得：

对于每个正例x，H(x)=True；

对于每个负例x，H(x)=False。

现在要考虑如何构造这样的H。

首先，每个实例本身是合取式，比如每个样例的每个属性都有一个确定的值。而假设是析取式，每个项是某个属性等于某个值。

例如，假设有一个正例，那么为了使得假设H能够覆盖这个正例，H中的某个项必须在这个实例中成立。比如，假设H中的某一项是a2=F，而该正例中a2=F，那么这个项就成立，整个H也就成立。所以，对于正例来说，H必须至少包含一个在该实例中成立的项。

而对于负例来说，H中的每一个项在该负例中都不成立。否则，如果某个项在负例中成立的话，那么H整体就成立，这会导致错误分类。

因此，H的构造必须满足：

对于所有正例，至少存在一个项在正例中成立；

对于所有负例，所有项在该负例中都不成立。

那么，如何构造这样的H？

一个思路是，从所有可能的候选项（即每个属性取T或F的约束）中，选出那些在负例中都不成立的项，然后用这些项的析取来覆盖所有正例。

具体来说，每个候选项是形如 ai=T 或 ai=F。这样的项共有2n个可能。然后，我们需要选择其中的某些项，使得：

1. 每个选中的项在所有的负例中都不成立。也就是说，对于每个选中的项，每个负例在该项对应的属性上取的值与该项的条件相反。例如，如果项是a1=T，那么所有负例的a1必须是F。否则，该负例会导致这个项成立，从而假设H被满足，这就会导致错误。

2. 对于每个正例，至少有一个选中的项在该正例中成立。

因此，问题转化为：找出所有满足在负例中不成立的项，然后这些项构成的析取是否覆盖所有正例。如果存在这样的项集合，那么取它们的析取作为假设即可。

那么，具体步骤可能如下：

步骤一：筛选出所有可能的候选项，这些候选项在所有的负例中都不成立。也就是说，对于每个属性ai的可能取值条件（ai=T或ai=F），检查是否所有负例在该属性上的值都不满足该条件。比如，对于项ai=T，如果所有负例的ai都是F，那么该候选项可以被保留；否则，必须排除这个候选项。

步骤二：检查这些被保留的候选项中，是否存在至少一个集合，使得它们的析取覆盖所有正例。或者说，每个正例至少满足其中一个候选项的条件。

如果存在这样的候选项集合，那么将这些候选项析取起来，就构成所求的假设H。否则，不存在这样的假设。

那么，如何高效地进行步骤一和步骤二？

步骤一的时间复杂度：对于每个候选项（共有2n个，每个属性有两个可能的约束），检查所有负例是否都不满足该候选项的条件。例如，对于候选项ai=T，检查所有负例的ai是否为F。如果是，则保留该候选项。否则，舍弃。这一步的时间是O(m_neg * 2n)，其中m_neg是负例的数量。因为每个候选项要检查m_neg次判断。

步骤二：需要确定是否存在被保留的候选项，使得每个正例至少满足其中一个。这时候，这相当于集合覆盖问题吗？比如，每个候选项可以覆盖某些正例，问题是要用最少的候选项覆盖所有正例。但这里的问题可能不需要最小，只要存在这样的覆盖即可。但因为我们需要找到是否存在这样的覆盖，所以可能需要更高效的算法。

不过，题目要求的是输出一个一致的假设，如果存在的话。那么，这时候是否可以将所有被保留的候选条件作为析取式？即，将步骤一筛选出来的所有候选项全部析取起来，构成H。这样是否满足条件？

假设步骤一之后，所有保留下来的候选项都不在任何负例中成立。那么，将这些候选项析取起来构成的假设H，在负例中必然不成立，因为每个候选项在负例中都不成立，析取后的整体也不成立。而对于正例，如果每个正例至少满足其中一个候选项，则H正确分类所有正例。否则，如果存在某个正例不满足任何候选项，那么H无法正确分类它，所以这种情况不存在一致的假设。

所以，算法可以是：

1. 对每个可能的候选项（ai=T或ai=F），检查是否该候选项在所有负例中都不成立。如果是，则保留。

2. 收集所有被保留的候选项，构成假设H，即它们的析取。

3. 检查这个H是否覆盖所有正例。如果是，则输出H；否则，不存在一致的假设。

但这样是否正确？

例如，假设所有被保留的候选项的析取是否覆盖所有正例？

是的。因为如果一个正例没有被任何被保留的候选项覆盖，那么该正例的每个属性取值条件都不在被保留的候选项中。即对于该正例中的每个ai=T的条件，候选项ai=T可能没有被保留，或者在步骤一中被排除了。但为什么会被排除？只有在存在至少一个负例中ai=T的情况下才会被排除。但该正例的ai=T，如果某个负例中存在ai=T的情况，那么这个候选项ai=T会被排除。所以，这样的正例的某个属性条件可能不在保留的候选项中。这会导致该正例无法被覆盖。因此，必须确保所有正例至少有一个候选项在保留列表中成立。

因此，当保留的候选项的析取无法覆盖所有正例时，则不存在一致的假设。反之，当存在时，该假设就是正确的。

所以，算法的大体步骤是：

• 收集所有满足条件的候选项，即它们在所有负例中都不成立。

• 然后，检查这些候选项中是否每个正例至少有一个成立。如果是，则输出它们的析取；否则，不存在解。

这样，整个算法的时间复杂度是怎样的？

假设样例数目是m=m_pos + m_neg。那么步骤一中，每个候选项的数目是2n，每个候选项要检查所有负例是否都不满足。例如，对于候选项ai=T，检查所有负例中ai是否为F。这需要对于每个候选项，遍历所有m_neg个负例，每个检查是否对应属性是否不符合候选项的条件。每个候选项的检查时间是O(m_neg)。所以步骤一的时间是O(2n * m_neg) = O(nm_neg)。

步骤二中，收集到的候选项可能有k个。然后，对于每个正例，需要检查是否存在至少一个候选项在该正例中成立。每个正例的检查时间是O(k)。总共有m_pos个正例，所以步骤二的时间是O(k * m_pos)。而k最多是2n，所以总时间是O(n m_pos)。

步骤三，如果步骤二通过，则输出所有候选项的析取式，否则输出不存在。

那么，总的时间复杂度是O(n(m_neg + m_pos))，即多项式时间，符合题目要求。

那这样的算法是否正确？

例如，假设有一个正例，它对应的属性值组合中，没有任何一个候选项被保留。那么该正例无法被覆盖，所以不存在解。否则，当所有正例至少有一个被保留的候选项成立时，输出这些候选项的析取式即可。此时，所有负例都不满足任何一个候选项，所以整个析取式在负例上不成立。而正例都满足至少一个候选项，所以成立。因此，这样得到的H是符合要求的。

因此，这个算法是正确的。

现在，具体如何实现？

例如，假设输入是一组正例和负例，每个实例是n个布尔值的合取。我们需要：

1. 对于每个可能的候选项c（ai=T或ai=F），检查是否所有负例的ai值与c的条件相反。如果是，保留c。

2. 收集所有保留的候选项，构成集合C。

3. 对于每个正例，检查是否存在至少一个c ∈ C，使得该正例满足c。

4. 如果所有正例都满足，则输出C中所有项的析取；否则，输出不存在。

那这确实是一个多项式时间的算法，因为步骤1是O(nm_neg)，步骤3是O(nm_pos)。总时间复杂度是O(n(m_neg + m_pos))，而n和样例数目都是输入参数的多项式。

那如何举例说明？

比如，考虑n=2的情况。正例可能是(a1=T, a2=F)，负例可能是(a1=F, a2=F)。则候选项包括a1=T, a1=F, a2=T, a2=F。

对于负例中的每个属性：

负例的a1=F，所以候选项a1=T是否在负例中成立？不成立，因为负例的a1=F。所以如果候选项a1=T是否在所有负例中都成立？这需要看所有负例的a1是否都为T。如果有负例的a1=F，那么候选项a1=T在负例中的情况是False，所以该候选项的条件是ai=T，而负例中该属性是F，所以候选项在负例中不成立。这时候，如果所有负例中的ai都满足该候选项的条件的反面，那么该候选项被保留。

例如，对于候选项a1=T，如果所有负例的a1都是F，则该候选项被保留。否则，如果有某个负例的a1=T，则候选项a1=T在该负例中成立，所以该候选项会被排除。

所以，步骤一中的候选项保留的条件是：该候选项的条件在所有负例中都不成立。

例如，假设有一个负例中的a1=F，另一个负例中的a1=T。那么，候选项a1=T会被排除，因为有负例满足a1=T。而候选项a1=F会被检查是否所有负例的a1=F？如果有负例的a1=T，则候选项a1=F的条件在那些负例中不成立（即，该负例的a1=T，不满足a1=F的条件），所以候选项a1=F是否被保留？需要检查所有负例是否都不满足该候选项的条件。例如，候选项a1=F的条件是a1=F。如果有负例中的a1=T，则候选项a1=F在该负例中的情况是False，所以该候选项是否满足在所有负例中都不成立？

或者，可能我在这里弄反了条件？

候选项c的条件是，比如ai=T。当在某个实例中ai=T时，c的条件成立。否则，不成立。所以，对于候选项ai=T来说，如果该候选项在某个负例中成立（即该负例的ai=T），那么该候选项会被排除，因为它会导致H在该负例中成立。因此，候选项c必须满足：在所有负例中，c的条件都不成立。所以，候选项ai=T的条件成立的条件是实例的ai=T。如果在任何一个负例中，ai=T，那么该候选项不能被保留，因为该候选项会导致H在那些负例中成立，导致错误分类。

因此，步骤一中的正确做法是，对于每个候选项c，检查是否对于所有负例，c的条件在该负例中不成立。如果是，则保留c。

例如，候选项c是ai=T的条件。要保留c，当且仅当每个负例中的ai都是F。这样，当H中包含c时，在负例中，c的条件不成立，因此整个H的析取式也不成立。

那现在，如何正确收集这些候选项？

比如，对于每个属性ai，有两个可能的候选项：ai=T和ai=F。对于每个候选项，检查所有负例是否都不满足该候选项的条件。例如，对于候选项ai=T来说，检查所有负例中的ai是否等于F。如果是，则保留该候选项。否则，不保留。同样，对于候选项ai=F来说，检查所有负例中的ai是否等于T。如果是，则保留。

那么，在步骤一中，每个候选项c对应的条件就是，所有负例都不满足c的条件。或者说，对于所有负例x，x不满足c的条件。

例如，c是ai=T，那么对于所有x ∈ 负例，x的ai=F。这样，c的条件在负例中不成立，所以可以保留。

现在，步骤一完成后，我们得到一个候选集合C，其中每个候选项c都不在任何负例中成立。那么，在步骤二中，检查所有正例是否至少有一个c ∈ C满足该正例的条件。

如果每个正例至少有一个c在C中满足，那么将这些c析取起来得到H，即可正确分类所有正例和负例。否则，不存在这样的H。

例如，假设有一个正例x，它的每个属性的取值对应的候选项都不在C中。例如，x的a1=T，但候选项a1=T不在C中（因为存在某个负例的a1=T），而x的a2=F，但候选项a2=F也不在C中（因为存在某个负例的a2=F）。那么，此时该正例无法被覆盖，因此不存在一致的假设。

所以，这个算法是正确的。

综上，算法步骤可以总结为：

1. 收集所有可能的候选项（ai=T和ai=F，共2n个）。

2. 筛选出其中满足“在所有负例中都不成立”的候选项，构成集合C。

3. 检查每个正例是否至少被集合C中的一个候选项覆盖。

• 对于每个正例，遍历C中的每个候选项，如果该正例满足该候选项的条件，则标记该正例为覆盖。

4. 如果所有正例都被覆盖，则输出C中所有候选项的析取式；否则，输出不存在这样的假设。

这个算法的时间复杂度为O(n * m_neg)（步骤2）加上O(m_pos * |C|)。而|C|最多为2n，所以总时间复杂度是O(n(m_neg + m_pos))，满足多项式时间的要求。

那现在需要将这个算法具体实现，或者写出伪代码？

根据问题描述，只需要设计算法，可能不需要具体代码，但需要明确步骤。

例如，算法的伪代码可能如下：

输入：训练样例集合S = {(x1, y1), (x2, y2), ..., (xm, ym)}，其中每个xi是n维布尔属性，yi∈{+1, -1}（假设+1为正例，-1为负例）

输出：一个假设H（属性约束的析取），或声明不存在。

步骤：

1. 将样例分为正例集合P和负例集合N。

2. 初始化候选集合C为空。

3. 对于每个属性ai（i从1到n）：

a. 检查候选项ai=T是否满足：所有负例中的ai的值为F。

i. 遍历所有负例x ∈ N：

• 如果存在x的ai = T，则该候选项不满足条件，跳过。

ii. 如果所有负例的ai都是F，则将ai=T加入C。

b. 检查候选项ai=F是否满足：所有负例中的ai的值为T。

i. 遍历所有负例x ∈ N：

• 如果存在x的ai = F，则该候选项不满足条件，跳过。

ii. 如果所有负例的ai都是T，则将ai=F加入C。

4. 对于每个正例x ∈ P：

a. 检查是否存在候选项c ∈ C，使得x满足c的条件。

i. 例如，对于候选项ai=T，检查x的ai是否为T。

b. 如果存在这样的c，则继续；否则，输出不存在一致假设。

5. 如果所有正例都被覆盖，则输出C中的候选项的析取式；否则，输出不存在。

这样，算法的时间复杂度主要是在步骤3和步骤4。

步骤3中，每个属性的两个候选项需要检查所有负例，每个候选项的时间是O(m_neg)。总共有2n个候选项，所以步骤3的时间是O(2n * m_neg) = O(n m_neg)。

步骤4中，每个正例需要检查最多2n个候选项中的每个是否满足。每个正例的时间是O(2n)。总共有m_pos个正例，所以步骤4的时间是O(2n m_pos) = O(n m_pos)。

总的时间复杂度为O(n (m_neg + m_pos))，这显然是关于n和样例数的多项式时间。

所以，这个算法满足题目的要求。

要解决这个问题，我们需要设计一个算法，从训练样例中学习一个一致的假设（如果存在）。假设空间由布尔属性的析取式构成，每个假设必须正确分类所有正例和负例。

方法思路

• 筛选有效候选项：对于每个属性，检查其两种可能取值（T/F）是否在所有负例中均不成立。若满足，则保留该候选项。

• 验证正例覆盖：确保所有正例至少被一个保留的候选项覆盖。若存在这样的候选项集合，则输出它们的析取式作为假设；否则，输出不存在。

该算法的时间复杂度为O(n(m_neg + m_pos))，其中n是属性数，m_neg和m_pos分别是负例和正例的数量，满足多项式时间要求。

解决代码

代码解释

• 分割正负例：将输入样例按标签分为正例和负例。
• 筛选候选项：对每个属性检查其两种取值是否在所有负例中均不成立，保留有效候选项。
• 验证覆盖：检查每个正例是否至少被一个候选项覆盖，若所有正例均被覆盖，则构造析取式作为假设；否则返回不存在。

该算法高效地筛选出满足条件的候选项，并验证其覆盖性，确保输出的假设在多项式时间内满足所有训练样例。